Auflistung nach Schlagwort "computational complexity"

Auflistung nach Schlagwort "computational complexity"

Sortiert nach: Sortierung: Ergebnisse:

  • Applications of matching theory in constraint programming 
    Cymer, Radosław (Hannover : Gottfried Wilhelm Leibniz Universität Hannover, 2013)
    [no abstract]
  • Computational aspects of dependence logic 
    Lohmann, Peter (Hannover : Gottfried Wilhelm Leibniz Universität Hannover, 2012)
    [no abstract]
  • A fragment of dependence logic capturing polynomial time 
    Ebbing, Johannes; Kontinen, Juha; Mueller, Julian-Steffen; Vollmer, Heribert (Braunschweig : Tech. Univ. Braunschweig, 2014)
    In this paper we study the expressive power of Horn-formulae in dependence logic and show that they can express NP-complete problems. Therefore we define an even smaller fragment D*-Horn and show that over finite successor ...
  • On second-order monadic monoidal and groupoidal quantifiers 
    Kontinen, Juha; Vollmer, Heribert (Braunschweig : Tech. Univ. Braunschweig, 2010)
    We study logics defined in terms of second-order monadic monoidal and groupoidal quantifiers. These are generalized quantifiers defined by monoid and groupoid word-problems, equivalently, by regular and context-free ...
  • The Tractability of Model-checking for LTL: The Good, the Bad, and the Ugly Fragments 
    Bauland, Michael; Mundhenk, Martin; Schneider, Thomas; Schnoor, Henning; Schnoor, Ilka; Vollmer, Heribert (Amsterdam : Elsevier, 2009)
    In a seminal paper from 1985, Sistla and Clarke showed that the model-checking problem for Linear Temporal Logic (LTL) is either NP-complete or PSPACE-complete, depending on the set of temporal operators used. If, in ...